Camille du Locle, giám đốc nghệ thuật của Opéra-Comique, đã đặt hàng Bizet viết một vở opera dựa trên tiểu thuyết của Mérimée vào đầu năm 1873 để khởi diễn vào cuối năm. Tuy nhiên, khó khăn trong việc tìm kiếm vai nữ chính (leading lady) đã làm việc tập vở chậm trễ đến tận tháng 8 năm 1874. Bizet đã mua một ngôi nhà tại Bougival trên bờ sông Seine, nơi ông hoàn thành bảng dàn bè piano (piano score) vào mùa hè năm 1874, và mất hai tháng nữa để hoàn thành toàn bộ bản hoà âm.

Sau khi tiếp cận với ca sĩ Marie Roze, người khước từ tham gia, du Locle đề xuất vai diễn với giọng nữ trung (mezzo-soprano) là Célestine Galli-Marié. Những cuộc đàm phán tài chính về chi phí tham gia tiếp tục, và bà đã chấp nhận tham gia vào tháng 12 năm 1873, với mức giá 2,500 franc mỗi tháng trong bốn tháng. Rõ ràng bà đã không biết tới tiểu thuyết của Mérimée.

Trong thời gian tập vở, trợ lý của du Locle là de Leuven đã lên tiếng lo ngại về cốt truyện của vở opera, và gây sức ép với Bizet và những người viết lời thay đổi phần kết kiểu bi kịch. De Leuven cảm thấy rằng các gia đình sẽ bị sốc khi xem một vở opera "đồi truỵ" đến như vậy trên sân khấu Opéra-Comique vốn đã có danh tiếng là một nhà hát gần gũi với các gia đình, với nhiều lô được các bậc cha mẹ sử dụng để phỏng vấn trước người con rể tương lai của họ. Những người viết lời đã đồng ý thay đổi phần kết, nhưng Bizet từ chối, trực tiếp dẫn tới việc de Leuven rút lui khỏi nhà hát đầu năm 1874.

Những người viết lời đã làm dịu bớt một số yếu tố quá cực đoan trong tiểu thuyết của Mérimée, dù đã có lời phàn này rằng điều này, và sự tham gia gần gũi của Bizet vào việc hình thành lời thoại chủ yếu là để thực hiện mong muốn cho vở opera gần gũi hơn với tác phẩm của Pushkin mà thôi.[11]

Việc tập toàn vở bắt đầu tháng 10 năm 1874. Dàn nhạc của Opéra-Comique tuyên bố bản nhạc là không thể chơi được, và việc phân phối các vai diễn gặp khó khăn theo các chỉ đạo của Bizet. Tuy nhiên, sự phản đối mạnh nhất chính là từ du Locle,[12] người ưa thích Bizet về mặt cá nhân, nhưng ghét opera. Ở giai đoạn này, Opéra-Comique đang gặp khó khăn về tài chính, dẫn tới việc du Locle tin rằng opera sẽ làm cho công ty gặp thêm khó khăn, thể loại này đã không hề mang lại một thành công thực sự nào từ vở Faust của Charles Gounod.

Những người viết lời, mà đối với họ Carmen "không quan trọng mấy" (họ có bốn vở opera khác đang diễn ở Paris ở thời điểm đó), bí mật tìm cách xúi giục các ca sĩ bi kịch hoá vở diễn nhằm mục đích làm giảm ảnh hưởng của tác phẩm. Tuy nhiên, với sự vui sướng của Bizet, những buổi tập cuối cùng dường như đã thuyết phục được đa số nhà chuyên môn về opera.